package 归并排序;

import java.io.*;

/**
 * @author ljb
 * @version 1.0
 * @Date 2024/10/18
 */
public class MergeSort {
    public static int MAXN = 1000001;
    public static int[] arr = new int[MAXN];
    public static int[] help = new int[MAXN];
    public static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n = (int) in.nval;
        for(int i = 0; i < n; i++){
            in.nextToken();
            arr[i] = (int) in.nval;
        }
        mergeSort1(0, n-1);
        for(int i = 0; i < n-1; i++){
            out.print(arr[i] + " ");
        }
        out.println(arr[n-1]);
        out.flush();
        out.close();
        br.close();
    }

    // 归并排序递归版
    // 假设l...r一共n个数
    // T(n) = 2 * T(n/2) + O(n)
    // a = 2, b = 2, c = 1
    // 根据master公式，时间复杂度O(n * log n)
    // 空间复杂度O(n)
    public static void mergeSort1(int l, int r){
        if(l == r){
            return;
        }
        int m = (l + r) / 2;
        mergeSort1(l, m);
        mergeSort1(m+1, r);
        merge(l, m, r);
    }

    // 归并排序非递归版
    // 时间复杂度O(n * log n)
    // 空间复杂度O(n)
    public static void mergeSort2(){
        //一共发生O(log n)
        for(int l, m, r, step=1; step < n; step <<= 1){
            l = 0;
            while(l < n){//O(n)
                m = l + step-1;
                if(m+1 >= n){
                    break;
                }
                r = Math.min(l + (step << 1) -1, n-1);
                //l...m m+1...r
                //             l...m m+1...r
                //                          l...m m+1..r
                merge(l, m, r);
                l = r+1;
            }
        }
    }

    //O(n)
    public static void merge(int l, int m, int r){
        int i = l;
        int a = l;
        int b = m+1;
        while(a <= m && b <= r){
            help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while(a <= m){
            help[i++] = arr[a++];
        }
        while(b <= r){
            help[i++] = arr[b++];
        }
        for(i = l; i <= r; i++){
            arr[i] = help[i];
        }
    }
}
